package sat;

import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import sat.convenience.Population;
import sat.convenience.Solution;
import sat.convenience.VariationMap;
import sat.convenience.VariationMaps;

/**
 * Klasa zawiera zbiór funkcji wykorzystywanych w implementacji algorytmu evolucyjnego
 * @author bawey
 */
public class EvosatToolkit {
    
    /**
     * Funkcja generująca populację rozwiązań
     * @param size porządana liczność populacji
     * @param solution rozwiązanie początkowe. Wartości przypisań są ignorowane.
     * @return uzyskana populacja
     */
    public static Population generatePopulation(int size, Solution solution) {
        Population population = new Population();
        population.ensureCapacity(size);
        for (int i = 0; i < size; ++i) {
            population.add(GsatToolkit.randomize(solution));
        }
        return population;
    }

    /**
     * Funkcja przeszukuje populację w nadziei znalezienia podstawienia spełniającego
     * formułe.
     * @param formula formuła logiczna
     * @param population populacja
     * @return szukane podstawienie lub null
     */
    public static Solution evaluatePopulation(FormulaCNF formula, Population population) {
        for (int i = 0; i < population.size(); ++i) {
            if (formula.evaluate(population.get(i))) {
                return population.get(i);
            }
        }
        return null;
    }

    /**
     * Funkcja generuje populację pośrednią
     * @param formula formuła logiczna, względem której weryfikowane jest przystosowanie osobników
     * @param srcPopulation populacja źródłowa
     * @param intermediateToParentsRatio stosunek liczności populacji macierzystej
     *        do liczności wygenerowanej populacji
     * @return wygenerowana populacja
     */
    public static Population generateOffspring(FormulaCNF formula, Population srcPopulation, int intermediateToParentsRatio) {
        intermediateToParentsRatio=Math.max(intermediateToParentsRatio, 1);
        Population dstPopulation = new Population();
        float values[] = new float[srcPopulation.size()];
        for (int i = 0; i < srcPopulation.size(); ++i) {
            values[i] = formula.getTrueClausesPercentage(srcPopulation.get(i));
        }
        float[] distribution = getDistribution(values);
        //fill the new population
        for (int i = 0; i < srcPopulation.size()*intermediateToParentsRatio; ++i) {
            dstPopulation.add(createOneChild(srcPopulation, distribution));
        }
        return dstPopulation;
    }

    /**
     * Funkcja generuje koło ruletki dla populacji. Koło odwzorowane jest na przedział liczbowy 0-1,
     * a każdemu z odcinków przypisany jest jego podprzedział, proporcjonalny do wartości funkcji
     * przystosowania danego osobnika. I-ta wartość w zwracanej tablicy odpowiada końcowi przedziału
     * przydzielonemu itemu osobnikowi. Początek tego porzedziału to koniec poprzedniego lub 0
     * (dla pierwszego osobnika). Koło ruletki jest wykorzystywane przy doborze rodziców.
     * @param values wartości funkcji przystosowania
     * @return krańce przedziałów przypisanych każdemu z osobników.
     */
    private static float[] getDistribution(float[] values) {
        float[] result = new float[values.length];
        float sum = 0f;
        for (float value : values) {
            value = (float) Math.pow(value, 10);
            sum += value;
        }
        //System.out.println(" avg quality: " + sum / values.length);
        //System.err.println("= "+sum);
        for (int i = 0; i < values.length; ++i) {
            float prev = (i == 0 ? 0f : result[i - 1]);
            result[i] = prev + values[i] / sum;
            //System.err.println(i+"th value: "+result[i]);
        }
        return result;
    }

    /**
     * Na podstawie koła ruletki funkcja dobiera dwa osobniki potomne i tworzy zwraca jeden potomny.
     * @param srcPopulation populacja źródłowa
     * @param distribution koło ruletki
     * @return potomny osobnik
     */
    private static Solution createOneChild(Population srcPopulation, float[] distribution) {
        float rand1 = (float) Math.random();
        float rand2 = (float) Math.random();
        int i1 = -1, i2 = -1;
        for (int i = 0; i < distribution.length; ++i) {
            float prev = (i == 0 ? 0f : distribution[i - 1]);
            if (rand1 > prev && rand1 <= distribution[i]) {
                i1 = i;
            }
            if (rand2 > prev && rand2 <= distribution[i]) {
                i2 = i;
            }
        }
        if (i1 == -1) {
            i1 = 0;
        }
        if (i2 == -1) {
            i2 = 0;
        }
        //so i1 and i2 are the parents chosen for breeding. cool, huh?
        return crossSolutions(srcPopulation.get(i1), srcPopulation.get(i2));
    }

    /**
     * Funkcja tworząca rozwiązanie na podstawie losowego krzyżowania dwóch osobników rodzicielskich.
     * Wartość każdego z podstawień jest losowo dziedziczona po jednym z rodziców.
     * @param meat1 pierwszy rodzic
     * @param meat2 drugi rodzic
     * @return potomek
     */
    private static Solution crossSolutions(Solution meat1, Solution meat2) {
        Solution child = new Solution();
        for (Iterator it = meat1.keySet().iterator(); it.hasNext();) {
            String key = (String) it.next();
            child.put(key, Math.random() > 0.5 ? meat1.get(key) : meat2.get(key));
        }
        return child;
    }

    /**
     * Funkcja wprowadza mutacje poprzez losowe negowanie niektórych przypisań.
     * @param lambda populacja bez mutacji
     * @param probability prawdopodobieństwo zajścia mutacji dla każdego z przypisań.
     * @return populacja zawierająca tak osobniki sprzed, jak i po mutacji
     */
    
    public static Population applyMutations(Population lambda, float probability) {
        Population mutants = new Population();
        for (Iterator<Solution> it = lambda.iterator(); it.hasNext();) {
            Solution solution = (Solution) it.next().clone();
            mutants.add((Solution)solution.clone());
            boolean hasChanged=false;
            for (Iterator<String> sit = solution.keySet().iterator(); sit.hasNext();) {
                String key = sit.next();
                if (Math.random() < probability) {
                    hasChanged=true;
                    solution.put(key, solution.get(key).booleanValue() ? Boolean.FALSE : Boolean.TRUE);
                }
            }
            if(hasChanged){
                mutants.add(solution);
            }
        }
        return mutants;
    }
    
    /**
     * Funkcja wybiera najlepsze spośród osobników populacji pośredniej, by utworzyły nową populację.
     * @param problem formuła logiczna stanowiąca rozwiązywany problem
     * @param mi populacja, wewnątrz której dokonywana jest selekcja
     * @param offspringOnly prawda, jeśli przekazana funkcji populacja zawiera wyłącznie osobniki potomne
     * @param limit limit osobników, które mają utworzyć nową populację
     * @return wynikowa populacja
     */
    public static Population performSelection(FormulaCNF problem, Population mi, boolean offspringOnly, int limit) {
        final FormulaCNF problem_copy = problem;

            Collections.sort(mi, new Comparator<Solution>() {

                @Override
                public int compare(Solution t, Solution t1) {
                    if (problem_copy.getTrueClausesPercentage(t) > problem_copy.getTrueClausesPercentage(t1)) {
                        return -1;
                    }
                    return 1;
                }
            });
            Population selection = (Population) mi.clone();
            for (int i = limit; i < selection.size(); ++i) {
                selection.removeElementAt(i);
            }
            return selection;
        
    }
}
